A multitude of applications include processes which require a step of measuring the variation between sets of random variables. These measurements may be stored or displayed in the form of a two-dimensional array. Such arrays are hereinafter referred to as covariance matrices.
One example of an application which requires the generation of a covariance matrix is the implementation of the IS-54 US Digital Cellular Radio Standard. This standard uses a speech coder known as Vector Sum Excited Linear Predictive Coding (VSELP), which requires the computation of a covariance matrix using as input a block of digital speech samples. The speech samples are stored at an 8 KHz sampling rate from an analog input. The details of the IS-54 Standard are discussed in EIA/TIA Document 2215 (Cellular System - Dual Mode Mobile Station/One State Compatibility Standard IS-54, December 1989).
The formula to generate a covariance matrix from 170 input speech samples is shown in Equation 1, where .phi.(i,k) represents the value at row i, column k, of the covariance matrix, N.sub.A represents the total number of input speech samples (N.sub.A =170), N.sub.P represents the maximum row and column number of the covariance matrix (N.sub.P =10), and S(x) represents the value of the xth input sample. ##EQU1##
A representation of a covariance matrix generated by Equation 1 is shown in FIG. 1A, where x,y represents the covariance measurement stored at row x, column y, of the covariance matrix.
FIG. 1B shows a possible method of storing the values of the covariance matrix shown in FIG. 1A in Random Access Memory (RAM). Note that only 66 RAM locations are needed to store an 11 by 11 covariance matrix, since a covariance matrix is symmetric. Thus, for every element .phi.(i,k) in a covariance matrix, .phi.(i,k)=.phi.(k,i). As a result, only the elements across the main diagonal and upper (or lower) triangle of a covariance matrix need be generated and stored to represent the entire covariance matrix.
FIG. 1C shows the storage configurations for three matrices, F, B, and C, which are subsets of the covariance matrix stored as shown in FIG. 1B. These three matrices are also symmetric.
Equation 1 displays redundancy in that if the row 0 elements of a covariance matrix (i.e. .phi.(0,0) to .phi.(0,10)) are generated, the remaining elements can be easily generated using Equation 2 shown below: EQU .phi.(i+1,k+1)=.phi.(i,k)+S(N.sub..rho. -i-1)S(N.sub..rho. -k-1)-S(N.sub.A -i-1)S(N.sub.A -k-1) (2)
The following equations show the derivation of Equation 2 for .phi.(1,1). EQU .phi.(0,0)=S(10)S(10)+S(11)S(11)+ . . . +S(169)S(169) EQU .phi.(1,1)=S( 9)S( 9)+S(10)S(10)+ . . . +S(168)S(168)
Therefore, EQU .phi.(1,1)=.phi.(0,0)+S(9)S(9)-S(169)S(169).
The implementation of Equation 2 is generally straightforward using multiply-accumulate hardware.
However, the row 0 elements (i.e. .phi.(0,0) to .phi.(0,10)) of a covariance matrix must first be generated by Equation 1 before the remainder of the matrix is generated by Equation 2.
The operands in the multiplications required by Equation 1 are samples offset from each other by a fixed number. For example, the formula to generate .phi.(0,1) is EQU .phi.(0,1)=S(10)S(9)+S(11)S(10)+ . . . +S(169)S(168).
In this example, the operands of every multiplication are samples offset from each other by one.
According to the prior art, to efficiently implement an equation having the form of Equation 1, a covariance matrix generator must include either two separate memories containing the 170 speech samples, or a pipeline on one memory containing the 170 samples. Block diagrams of these architectures are shown respectively in FIGS. 2 and 3.
Pipelining is a form of processing in which a functional unit performs its process in several steps. When the first step is completed, the results are passed to a second step that uses separate hardware. The first-step hardware is thus free to begin processing new data. While pipeline processing generally provides fast throughput for sequential processes, it is typically used for processes in which the time required to pass through some functional unit of a computer system would otherwise be longer than the intervals at which data may enter that functional unit.
The dual-memory architecture shown in FIG. 2 has the obvious disadvantage that it requires twice as much memory as the pipeline architecture shown in FIG. 3. However, when a covariance matrix generator employing the pipeline architecture shown in FIG. 3 generates, for example, .phi.(0,10), a 10 level pipeline is required. Such a pipeline provides for fast covariance matrix generation, but its purpose is uniquely confined to generating a covariance matrix. Such pipelines are not useful (in any obvious manner) for other calculations, such as, for example, the other parts of the computational requirement for VSELP.
Therefore, it is clearly desirable to provide an efficient covariance matrix generator that is easily used as a general purpose result store but which does not require the samples upon which the matrix is based to be stored in two banks of memory.
It is further desirable to provide a covariance matrix generator that efficiently implements covariance calculations at low hardware cost and supplies a useful "scratch pad" memory in the system for other calculations to store temporary results.